#include <fstream>
#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <Cstring>
#include <algorithm>
#include <string>
#include <set>
#include <iomanip>
#include <stack>
#include "CTReader.h"
#define N 50
#define KEYWORD_SIZE 18
#define OPERATOR_SIZE 9
#define DELIMITER_SIZE 6
#define separateline "-----"

using namespace std;

//定义一个文法类对象
Grammar grammar;
//定义FIRST集
FIRST first;
//定义·FOLLOW集
FOLLOW follow;
//是否为ll(1)文法
bool ll1 = true;
//定义预测分析表
string analyseTable[N][N];
//检测一个字符是否为非终结字符
bool isNonTerminal(char var);
//检测一个字符是否为空字
bool isEmpty(char var);
//检测一个字符是否为终结字符
bool isTerminal(char var);
void GrammarReader(const char *var);
//从控制台读取文法并保存
void readGrammar();
//判断一个产生式是否能求出FIRST集，能返回true，否则false
bool canCalFIRST(int i);
//计算能够计算FIRST集的产生式
void calFIRST();
//获取其非终结字符所在的索引
int getNonTerminalIndex(char var);
//检测第i个FIRST集是否有空字
bool hasEmpty(int i);
//判断是否能计算FIRST集(首字符含非终结符)
bool adjustFIRST(int i);
//计算两个集合的并集，即set(i) = set(i) ∪ set(j)
void calSetUnion(int i, int j);
//更新calCount
int reloadCalCount();
//计算FIRST集
void calFIRSTSet();
//输出first集
void printFIRST();
//获取索引（每一个非终结符在产生式的索引，索引保存在容器中）
void getPosition();
//将FIRST集去空加入FOLLOW集，i代表FOLLOW,i代表FIRST集
void calFollowAndFirstUnion(int i, int j);
//计算两个FOLLOW集的并集,即set(i) = set(i) ∪ set(j)
void calFollowAndFollowUnion(int i, int j);
//更新FOLLOW集的calCount
int reloadFOLLOWCalCount();
//计算FOLLOW集
void calFOLLOWSet();
//获取每一个非终结符的FOLLOW集
void getFollowSet();
//打印FOLLOW集
void printFOLLOW();
//获取终结符在Grammar.terminal[]中的索引
int getTerminalIndex(char var);
//构建单个产生式的First集,i,j为相应产生式的索引
set<char> buildFirstForOne(int i, int j);
//将产生式字符转为字符串,i,j为相应产生式的索引
string charToString(int i, int j);
//构建预测分析表
void bulidAnalyseTable();
//打印预测分析表
void printAnalyseTable();
//将vector中的字符转化为字符串
string veToString(vector<char> &vec);
//将字符数组有选择的转化为字符串
string toString(char buf[], int start, int end);
//核心函数，对语法进行分析
void Grammaranalyzer(string var);
//检查是否为LL(1)文法
void GrammarChecker();
//检查是否有左递归
char leftrecursion(list<char>::iterator it, char startpoint, string var);
//左递归初始化
void changerinit();
//消除间接左递归
void eliminateIndirectLeftRecursion();
//消除直接左递归
void eliminateDirectLeftRecursion();
//搜索
void dfs(int x);
//删除多余产生式
void removeUselessProduction();
//消除左递归
int reschanger();
//产生一个未使用的非终结符
string untergenerator();
//文法更新后重载新的文法
void reloadGrammar();
//提取左公共因子
void factorex();

/*
*测试数据
E G T H F
+ * ( ) i
E->TG
G->+TG|@
T->FH
H->*FH|@
F->(E)|i
*/
/*
E T G S F
+ - * / ( ) i
E->TG
G->+TG|-TG|@
T->FSj
S->*FS|/FS|@
F->(E)|i|@
*/

int main(int argc, char const *argv[])
{
    char const *file;
    char const *wordfile = "data_out1.txt";
    char ch;
    string s;
    // goto dbg;
    if (argc == 1)
    {
        cout << "No flie input." << endl;
        return 0;
    }
    else if (argc > 2)
    {
        cout << "Unexpect input." << endl;
        return 0;
    }
    file = argv[1];
// dbg:
//     file = "wenfa.txt";
    ifstream word(wordfile);
    if (!word.is_open())
    {
        cout << "Error in Opening file." << endl;
        return 0;
    }
    GrammarReader(file);
    GrammarChecker();
    reloadGrammar();
    GrammarReader("ll1.txt");
    factorex();
    calFIRSTSet();
    printFIRST();

    getFollowSet();
    printFOLLOW();
    bulidAnalyseTable();
    printAnalyseTable();
    while (word.get(ch) && ch != EOF)
    {
        s += ch;
    }

    Grammaranalyzer(s);

    return 0;
}

void GrammarReader(const char *file)
{
    int count = 0;
    int index = 0;
    //保存输入的第i行文法
    string str;
    char last;
    char buf[100] = {0};
    int i = 0;
    int stage = 0;
    ifstream rule(file);
    //临时保存非终结字符
    set<char> ter;
    if (!rule.is_open())
    {
        cout << "Error in Opening file." << endl;
        return;
    }
    rule.getline(buf, 100);
    while (buf[0] != 0)
    {
        string s = "";
        i = 0;
        count = 0;
        if (stage == 0)
        {
            for (i = 0; buf[i] != 0; i++)
            {

                if (buf[i] == ' ')
                {
                    if (s != "")
                    {
                        grammar.Untermial[count] = s;
                        count++;
                        s = "";
                    }
                }
                else
                {
                    s += buf[i];
                }
            }
            grammar.Untermial[count] = s;
            grammar.UnterNum = ++count;
            stage++;
            rule.getline(buf, 100);
            continue;
        }
        if (stage == 1)
        {
            for (i = 0; buf[i] != 0; i++)
            {

                if (buf[i] == ' ')
                {
                    if (s != "")
                    {
                        grammar.termial[count] = s;
                        count++;
                        s = "";
                    }
                }
                else
                {
                    s += buf[i];
                }
            }
            grammar.termial[count] = s;
            grammar.terminum = ++count;
            stage++;
            rule.getline(buf, 100);
            continue;
        }

        grammar.grammarTable[index][count].push_back(buf[i]);
        i += 3;
        while ((int)buf[i] != 0)
        {

            if ((int)buf[i] == 124)
            {
                count++;
                i++;
                grammar.grammarTable[index][count].push_back(buf[0]);
                grammar.grammarTable[index][count].push_back(buf[i]);
                if (isTerminal(buf[i]))
                {
                    ter.insert(buf[i]);
                }
                i++;
            }
            else
            {
                grammar.grammarTable[index][count].push_back(buf[i]);
                if (isTerminal(buf[i]))
                {
                    ter.insert(buf[i]);
                }
                i++;
            }
        }
        grammar.countEachRow[index] = count + 1;
        index++;
        rule.getline(buf, 100);
    }
    //保留文法个数
    grammar.count = index;
    //保存终结字符
    set<char>::iterator it = ter.begin();
    for (it; it != ter.end(); it++)
    {
        grammar.terminalChar[grammar.terNum] = *it;
        grammar.terNum++;
    }
    //注意需要把特殊符号"#"，加入
    grammar.terminalChar[grammar.terNum] = '#';
    grammar.terNum++;

    return;
}
void reloadGrammar()
{
    Grammar grammara;
    grammar = grammara;
}

bool isTerminal(char var)
{
    if (var == '#')
    {
        return true;
    }

    string s = "";
    s += var;
    for (int i = 0; i < grammar.terminum; i++)
    {
        if (grammar.termial[i].compare(s) == 0)
        {
            return true;
        }
    }
    return false;
}
//检测一个字符是否为非终结字符
bool isNonTerminal(char var)
{
    string s = "";
    s += var;
    for (int i = 0; i < grammar.UnterNum; i++)
    {
        if (grammar.Untermial[i].compare(s) == 0)
        {
            return true;
        }
    }
    return false;
}
bool isNonTerminal(string s)
{

    for (int i = 0; i < grammar.UnterNum; i++)
    {
        if (grammar.Untermial[i].compare(s) == 0)
        {
            return true;
        }
    }
    return false;
}
//检测一个字符是否为空字
bool isEmpty(char var)
{
    if ((int)var == 64)
    {
        return true;
    }
    else
    {
        return false;
    }
}
//获取其非终结字符所在的索引
int getNonTerminalIndex(char var)
{
    int index = 0;
    //获取其终结字符所在的索引
    for (index; index < grammar.count; index++)
    {
        if ((int)var == (int)grammar.grammarTable[index][0].front())
        {
            break;
        }
    }
    return index;
}
//检测第i个FIRST集是否有空字
bool hasEmpty(int i)
{
    set<char>::iterator it = first.First[i].begin();
    for (it; it != first.First[i].end(); it++)
    {
        if ((int)*it == 64)
        {
            return true;
        }
    }
    return false;
}
void GrammarChecker()
{
    char startpoint;
    for (int i = 0; i < grammar.count; i++)
    {
        //保存产生式的非终结符
        list<char>::iterator it1 = grammar.grammarTable[i][0].begin();
        startpoint = *it1;
        for (int j = 0; j < grammar.countEachRow[i]; j++)
        {
            list<char>::iterator it = grammar.grammarTable[i][j].begin();
            //判断产生式是否是自左递归的
            it++;
            if (*it == startpoint)
            {
                cout << "文法存在直接左递归" << endl;
                ll1 = false;
            }
            //判断产生式是否是间接左递归的
            else if (isNonTerminal(*it))
            {
                char curs = leftrecursion(it, startpoint, "");
                if (curs)
                {
                    cout << "文法存在间接左递归" << endl;
                    ll1 = false;
                    return;
                }
            }
        }
    }
    reschanger();
}
//提取左公共因子
void factorex()
{

    for (int i = 0; i < grammar.count; i++)
    {

        for (int j = 0; j < grammar.countEachRow[i]; j++)
        {
            string factor = "";
            //保存产生式的因子
            list<char>::iterator it = grammar.grammarTable[i][j].begin();
            *it++;
            //从左读取产生式
            for (it; it != grammar.grammarTable[i][j].end(); it++)
            {
                factor += *it;
                //读取字符
            }
            for (int k = 0; k < factor.length(); k++)
            {
                for (int l = j + 1; l < grammar.countEachRow[i]; l++)
                {
                    list<char>::iterator tmp = grammar.grammarTable[i][l].begin();
                    string s = "";
                    for (int o = 0; o < factor.length() - k; o++)
                    {
                        tmp++;
                        if (tmp == grammar.grammarTable[i][l].end())
                        {
                            break;
                        }

                        s += *tmp;
                        //读取等长字符
                    }
                    if (factor.substr(0, factor.length() - k).compare(s) == 0)
                    {
                        ll1 = false;
                        //找到出现因子的产生式
                        int index = 0;

                        list<char>::iterator tochange = grammar.grammarTable[i][j].begin();
                        //产生一个新的非终结符
                        char newword = untergenerator().c_str()[0];
                        //创建新的产生式
                        grammar.grammarTable[grammar.count][index].push_back(newword);
                        //先处理第i，j号产生式
                        list<char>::iterator mov = grammar.grammarTable[i][j].begin();
                        //标记是否新产生了空字
                        bool flag = false;
                        mov++;
                        //移动至公因子后
                        for (int r = 0; r < factor.length() - k; r++)
                        {
                            mov++;
                            if (mov == grammar.grammarTable[i][j].end())
                            {
                                //如果恰巧这个产生式只有公因子，则把空加入新的产生式
                                grammar.grammarTable[grammar.count][index++].push_back('@');
                                flag = true;
                                break;
                            }
                        }
                        //辅助删除
                        int con = 0;
                        for (mov; mov != grammar.grammarTable[i][j].end(); mov++)
                        {
                            //读取本产生式，复制并把后面的删除，改为新的非终结符
                            grammar.grammarTable[grammar.count][index].push_back(*mov);
                            con++;
                        }
                        while (con > 0)
                        {
                            grammar.grammarTable[i][j].pop_back();
                        }
                        grammar.grammarTable[i][j].push_back(newword);
                        if (!flag)
                        {
                            index++;
                        }
                        grammar.grammarTable[grammar.count][index].push_back(newword);

                        //处理i，l产生式
                        flag = false;
                        mov = grammar.grammarTable[i][l].begin();
                        mov++;
                        //移动至公因子后
                        for (int r = 0; r < factor.length() - k; r++)
                        {
                            mov++;
                            if (mov == grammar.grammarTable[i][l].end())
                            {
                                //如果恰巧这个产生式只有公因子，则把空加入新的产生式
                                grammar.grammarTable[grammar.count][index++].push_back('@');
                                break;
                            }
                        }
                        for (mov; mov != grammar.grammarTable[i][l].end(); mov++)
                        {
                            //读取本产生式，复制
                            grammar.grammarTable[grammar.count][index].push_back(*mov);
                            con++;
                        }
                        //彻底删除这个产生式
                        for (int u = l; u < grammar.countEachRow[i]; u++)
                        {
                            grammar.grammarTable[i][u] = grammar.grammarTable[i][u + 1];
                        }
                        grammar.countEachRow[i]--;

                        if (!flag)
                        {
                            index++;
                        }
                        grammar.countEachRow[grammar.count] = 2;
                        grammar.count++;
                    }
                }
            }
        }
    }
    cout << "\n最终文法为" << endl;
    for (int i = 0; i < grammar.count; i++)
    {
        bool gg = true;
        for (int j = 0; j < grammar.countEachRow[i]; j++)
        {
            list<char>::iterator it = grammar.grammarTable[i][j].begin();
            if (gg)
            {
                cout << *it << "->";
                gg = false;
            }

            for (it++; it != grammar.grammarTable[i][j].end(); it++)
            {
                cout << *it;
            }
            if (j == grammar.countEachRow[i] - 1)
            {
                break;
            }

            cout << "|";
        }
        cout << endl;
    }
    cout << endl;
    string box[] = {"false", "true"};
    cout << "原文法是否为LL(1)文法：" << box[ll1] << endl
         << endl;
}

map<string, int> mp; //记录每个node的下标
vector<node> vnode;  //每一个产生式
string start;        //文法G[s]
bool used[maxn];     //用于去掉无用产生式
int ntt = 0;
//初始化工作
void changerinit()
{
    ntt = 0;
    mp.clear();
    vnode.clear();
    start = grammar.Untermial[0];
    for (int i = 0; i < grammar.count; i++)
    {
        for (int j = 0; j < grammar.countEachRow[i]; j++)
        {
            ntt++;
        }
    }
}
//消除间接左递归

void eliminateIndirectLeftRecursion()
{
    for (int i = 0; i < vnode.size(); i++)
    {
        for (int j = 0; j < i; j++)
        {
            vector<string> ans;
            set<string> &righti = vnode[i].right;

            set<string> &rightj = vnode[j].right;
            char ch = vnode[j].left[0]; //取所有Aj产生式的左部的非终结符
            set<string>::iterator iti, itj;
            for (iti = righti.begin(); iti != righti.end(); iti++)
            {
                if (iti->at(0) == ch) //如果当前产生式右部的非终结符和Aj相同
                    for (itj = rightj.begin(); itj != rightj.end(); itj++)
                        ans.push_back(*itj + iti->substr(1)); //进行替换操作,先存储起来
            }
            while (!righti.empty())
            {
                if (righti.begin()->at(0) != ch) //存储当前没有替换的产生式右部
                    ans.push_back(*righti.begin());
                righti.erase(righti.begin()); //被替换过的产生式右部也删除掉
            }

            for (int k = 0; k < ans.size(); k++) //将替换过的产生式右部进行更新操作
            {
                righti.insert(ans[k]);
            }
        }
    }
}
//消除直接左递归
void eliminateDirectLeftRecursion()
{
    for (int i = 0; i < vnode.size(); i++)
    {
        char ch = vnode[i].left[0];
        set<string> &right = vnode[i].right; //拿到当前右部
        set<string>::iterator it;
        string tmp = untergenerator(); //对非终结符更改
        bool flag = true;
        for (it = right.begin(); it != right.end(); it++)
        {
            if (it->at(0) == ch)
            {
                vnode.push_back(node(tmp));
                mp[tmp] = vnode.size();
                flag = false;
                break;
            }
        }
        int idx = mp[tmp] - 1;
        if (flag)
            continue; //对于非终结符不相同的产生式我们需要跳过
        vector<string> ans;
        set<string> &tmpSet = vnode[idx].right;
        tmpSet.insert("@"); //添加空字符
        while (!right.empty())
        {
            if (right.begin()->at(0) == ch)
                tmpSet.insert(right.begin()->substr(1) + tmp);
            else
                ans.push_back(right.begin()->substr(0) + tmp);
            right.erase(right.begin()); //删除掉原本产生式右部
        }
        for (int k = 0; k < ans.size(); k++)
            right.insert(ans[k]); //更新加入新的产生式右部
    }
}
//搜索
void dfs(int x)
{
    if (used[x])
        return;
    used[x] = 1; //将当前下标记录
    set<string>::iterator it = vnode[x].right.begin();
    for (; it != vnode[x].right.end(); it++)
    {
        for (int i = 0; i < it->length(); i++)
        {
            if (isupper(it->at(i)))
            { //判断是否是非终结符

                dfs(mp[it->substr(i, 1)] - 1);
            }
        }
    }
}
//去掉无用产生式
void removeUselessProduction()
{
    memset(used, 0, sizeof(used));
    int idx = mp[start] - 1;
    dfs(idx); //搜索
    cout << "消除左递归后文法:" << endl;
    vector<node> res;
    for (int i = 0; i < vnode.size(); i++)
        if (used[i]) //存储已经标记过的产生式
            res.push_back(vnode[i]);
    vnode.clear();
    vnode = res;
}

int reschanger()
{
    changerinit(); //初始化
    for (int i = 0; i < grammar.count; i++)
    {

        //输入产生式
        for (int j = 0; j < grammar.countEachRow[i]; j++)
        {
            list<char>::iterator it = grammar.grammarTable[i][j].begin();
            string tmp = "";
            tmp += *it; //拿到产生式的左部
            if (!mp[tmp])
            {
                vnode.push_back(node(tmp));
                mp[tmp] = vnode.size();
            }
            int idx = mp[tmp] - 1; //获取左部的下标
            tmp = "";
            for (it++; it != grammar.grammarTable[i][j].end(); it++)
            {
                tmp += *it;
            }

            vnode[idx].push(tmp);
        }
    }
    //确定开始节点
    int idx = vnode.size() - 1;
    start = vnode[idx].left[0];
    eliminateIndirectLeftRecursion(); //消除间接左递归
    eliminateDirectLeftRecursion();   //消除直接左递归
    removeUselessProduction();        //去掉无用产生式
    for (int k = 0; k < vnode.size(); k++)
    {
        vnode[k].print();
    }
    ofstream out("ll1.txt");
    for (int k = 0; k < vnode.size(); k++)
    {

        if (k == vnode.size() - 1)
        {
            out << vnode[k].left.c_str() << endl;
            break;
        }
        out << vnode[k].left.c_str() << " ";
    }
    char buf[100];
    buf[0] = '@';
    int bufsize = 1;
    for (int k = 0; k < vnode.size(); k++)
    {
        set<string>::iterator it = vnode[k].right.begin();
        for (; it != vnode[k].right.end(); it++)
        {
            const char *a;
            a = it->c_str();
            for (int l = 0; l < it->length(); l++)
            {
                bool flag = true;
                if (isNonTerminal(a[l]))
                {
                    continue;
                }
                for (int u = 0; u < bufsize; u++)
                {
                    if (a[l] == buf[u])
                    {
                        flag = false;
                        continue;
                    }
                }
                if (flag)
                {

                    out << a[l] << " ";
                    buf[bufsize] = a[l];
                    bufsize++;
                }
            }
        }
    }
    out << endl;

    for (int k = 0; k < vnode.size(); k++)
    {
        vnode[k].printtf(out);
    }
    return 0;
}
string untergenerator()
{
    string s;

    for (int i = 65; i < 91; i++)
    {
        s = "";
        s += i;
        bool flag = true;
        for (int j = 0; j < grammar.UnterNum; j++)
        {
            if (s == grammar.Untermial[j])
            {
                flag = false;
                break;
            }
        }
        if (flag)
        {
            grammar.Untermial[grammar.UnterNum] = s;
            grammar.UnterNum++;
            return s;
        }
    }
    return "";
}

char leftrecursion(list<char>::iterator it, char startpoint, string checkbox)
{
    checkbox += startpoint;
    for (int k = 0; k < grammar.count; k++)
    {
        list<char>::iterator tmp = grammar.grammarTable[k][0].begin();
        if (*it == *tmp)
        {
            for (int l = 0; l < grammar.countEachRow[k]; l++)
            {
                tmp = grammar.grammarTable[k][l].begin();
                tmp++;
                for (int i = 0; i < checkbox.length(); i++)
                {
                    if (*tmp == checkbox[i])
                    {
                        return *tmp;
                    }
                }

                if (isNonTerminal(*tmp))
                {
                    char curs = leftrecursion(tmp, *tmp, checkbox);
                    if (curs != 0)
                    {
                        return curs;
                    }
                    return leftrecursion(tmp, startpoint, checkbox);
                }
            }

            break;
        }
    }
    return 0;
}

//计算两个集合的并集，即set(i) = set(i) ∪ set(j)，其中set(j)中去除空字
void calSetUnion(int i, int j)
{
    set<char>::iterator it = first.First[j].begin();
    //如果有空字，则去空字
    if (hasEmpty(j))
    {
        for (it; it != first.First[j].end(); it++)
        {
            if (!isEmpty(*it))
            {
                first.First[i].insert(*it);
            }
        }
    }
    else
    {
        for (it; it != first.First[j].end(); it++)
        {
            first.First[i].insert(*it);
        }
    }
}
//更新calCount
int reloadCalCount()
{
    int count = 0;
    for (int i = 0; i < grammar.count; i++)
    {
        if (first.flag[i] == true)
        {
            count++;
        }
    }
    first.calCount = count;
    return count;
}
//计算FIRST集
void calFIRSTSet()
{
    while (reloadCalCount() != grammar.count)
    {
        //扫描每一个产生式
        for (int i = 0; i < grammar.count; i++)
        {
            //如果没有计算FIRST集
            if (!first.flag[i])
            {
                for (int j = 0; j < grammar.countEachRow[i]; j++)
                {
                    list<char>::iterator it = grammar.grammarTable[i][j].begin();
                    //获取产生式的首字符
                    it++;
                    //如果it没有到边界并且是非终结字符并且并且已经计算FIRST集并且FIRST含有空字
                    while (it != grammar.grammarTable[i][j].end() && isNonTerminal(*it) && first.flag[getNonTerminalIndex(*it)] && hasEmpty(getNonTerminalIndex(*it)))
                    {
                        first.nonTerminal[i] = grammar.grammarTable[i][0].front();
                        // first.flag[i] = true;
                        calSetUnion(i, getNonTerminalIndex(*it));
                        it++;
                    }
                    //如果it到边界，说明每个非终结符的FIRST集都已经计算出来，并且都含有空字
                    if (it == grammar.grammarTable[i][j].end())
                    {
                        //把空字加入
                        first.First[i].insert('@');
                        first.flag[i] = true;
                        continue;
                    }
                    //否则，it没有到边界
                    else
                    {
                        //如果*it为终结符
                        if (isTerminal(*it))
                        {
                            first.nonTerminal[i] = grammar.grammarTable[i][0].front();
                            first.flag[i] = true;
                            //把终结字符保存到FIRST集
                            first.First[i].insert(*it);
                        }
                        //如果是非终结符
                        else if (isNonTerminal(*it))
                        {
                            //如果已经计算过FIRST集，则把FIrst集加入
                            if (first.flag[getNonTerminalIndex(*it)])
                            {
                                first.nonTerminal[i] = grammar.grammarTable[i][0].front();
                                first.flag[i] = true;
                                calSetUnion(i, getNonTerminalIndex(*it));
                            }
                            //没有计算过
                            else
                            {
                                first.flag[i] = false;
                            }
                        }
                        //如果是空字
                        else
                        {
                            first.nonTerminal[i] = grammar.grammarTable[i][0].front();
                            first.flag[i] = true;
                            //把终结字符保存到FIRST集
                            first.First[i].insert(*it);
                        }
                    }
                }
            }
            //如果计算FIRST集
            else
            {
                continue;
            }
        }
    }
}
//输出first集
void printFIRST()
{
    cout << "FIRST集如下：" << endl;
    for (int i = 0; i < grammar.count; i++)
    {
        cout << "FIRST"
             << "(" << first.nonTerminal[i] << ")"
             << "=";
        set<char>::iterator it;
        for (it = first.First[i].begin(); it != first.First[i].end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    }
    cout << endl;
}
//获取索引（每一个非终结符在产生式的索引，索引保存在容器中）
void getPosition()
{
    for (int i = 0; i < grammar.count; i++)
    {
        list<char>::iterator it = grammar.grammarTable[i][0].begin();
        for (int j = 0; j < grammar.count; j++)
        {
            for (int k = 0; k < grammar.countEachRow[j]; k++)
            {
                list<char>::iterator itp = grammar.grammarTable[j][k].begin();
                itp++;
                for (itp; itp != grammar.grammarTable[j][k].end(); itp++)
                {
                    if ((int)*it == (int)*itp)
                    {
                        Position pos;
                        pos.x = j;
                        pos.y = k;
                        //记下其位置
                        follow.position[i].push_back(pos);
                    }
                }
            }
        }
    }
}
//将FIRST集去空加入FOLLOW集，i代表FOLLOW,i代表FIRST集
void calFollowAndFirstUnion(int i, int j)
{
    set<char>::iterator it = first.First[j].begin();
    //如果有空字，则去空字
    if (hasEmpty(j))
    {
        for (it; it != first.First[j].end(); it++)
        {
            if (!isEmpty(*it))
            {
                follow.Follow[i].insert(*it);
            }
        }
    }
    else
    {
        for (it; it != first.First[j].end(); it++)
        {
            follow.Follow[i].insert(*it);
        }
    }
}
//更新FOLLOW集的calCount
int reloadFOLLOWCalCount()
{
    int count = 0;
    for (int i = 0; i < grammar.count; i++)
    {
        if (follow.flag[i] == true)
        {
            count++;
        }
    }
    follow.calCount = count;
    return count;
}
//计算两个FOLLOW集的并集,即set(i) = set(i) ∪ set(j)
void calFollowAndFollowUnion(int i, int j)
{
    set<char>::iterator it = follow.Follow[j].begin();
    for (it; it != follow.Follow[j].end(); it++)
    {
        follow.Follow[i].insert(*it);
    }
}
//计算FOLLOW集
void calFOLLOWSet()
{
    //对于开始符号S，需将"#"加入其FOLLOW集
    follow.Follow[0].insert('#');
    while (reloadFOLLOWCalCount() != grammar.count)
    {
        for (int i = 0; i < grammar.count; i++)
        {
            //如果没有计算FOLLOW集，则计算
            if (!follow.flag[i])
            {
                vector<Position>::iterator it = follow.position[i].begin();
                for (it; it != follow.position[i].end(); it++)
                {
                    int m = (*it).x;
                    int n = (*it).y;
                    list<char>::iterator itp = grammar.grammarTable[m][n].begin();
                    //使其指向首字符
                    itp++;
                    for (itp; itp != grammar.grammarTable[m][n].end(); itp++)
                    {
                        if ((int)(*itp) == (int)grammar.grammarTable[i][0].front())
                        {
                            itp++;
                            break;
                        }
                    }
                    // itp不指向结尾，并且是非终结符并FIRST集含有空字，则继续检测
                    while (itp != grammar.grammarTable[m][n].end() && isNonTerminal(*itp) && hasEmpty(getNonTerminalIndex(*itp)))
                    {
                        int index = getNonTerminalIndex(*itp);
                        follow.nonTerminal[i] = grammar.grammarTable[i][0].front();
                        //将非终结符去空字的FIRST集加入FOLLOW集
                        calFollowAndFirstUnion(i, index);
                        itp++;
                    }
                    //如果itp没有指向end指针，说明该字符为终结字符或非终结字符或空字
                    if (itp != grammar.grammarTable[m][n].end())
                    {
                        if (isTerminal(*itp))
                        {
                            follow.nonTerminal[i] = grammar.grammarTable[i][0].front();
                            //将非终结字符加入FOLLOW集
                            follow.Follow[i].insert(*itp);
                            //标记已经计算该非终结符的FOLLOW集
                            follow.flag[i] = true;
                        }
                        else if (isNonTerminal(*itp))
                        {
                            int index = getNonTerminalIndex(*itp);
                            follow.nonTerminal[i] = grammar.grammarTable[i][0].front();
                            //将非终结符去空字的FIRST集加入FOLLOW集
                            calFollowAndFirstUnion(i, index);
                            //标记已经计算该非终结符的FOLLOW集
                            follow.flag[i] = true;
                        }
                        //空字什么也不做
                        else
                        {
                        }
                    }
                    // itp指向end指针
                    else
                    {
                        if (!follow.flag[m])
                        {
                            //如果没有计算则标记false
                            follow.flag[i] = false;
                        }
                        else
                        {
                            follow.nonTerminal[i] = grammar.grammarTable[i][0].front();
                            calFollowAndFollowUnion(i, m);
                            //标记已经计算该非终结符的FOLLOW集
                            follow.flag[i] = true;
                        }
                    }
                }
            }
        }
    }
}
//获取每一个非终结符的FOLLOW集
void getFollowSet()
{
    getPosition();
    calFOLLOWSet();
}
//打印FOLLOW集
void printFOLLOW()
{
    cout << "FOLLOW集如下：" << endl;
    for (int i = 0; i < grammar.count; i++)
    {
        cout << "FOLLOW"
             << "(" << follow.nonTerminal[i] << ")"
             << "=";
        set<char>::iterator it;
        for (it = follow.Follow[i].begin(); it != follow.Follow[i].end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    }
    cout << endl;
}
//获取终结符在Grammar.terminal[]中的索引
int getTerminalIndex(char var)
{
    for (int i = 0; i < grammar.terNum; i++)
    {
        if ((int)grammar.terminalChar[i] == (int)var)
        {
            return i;
        }
    }
    //不存在返回-1
    return -1;
}
//构建单个产生式的First集,i,j为相应产生式的索引
set<char> buildFirstForOne(int i, int j)
{
    //定义集合
    set<char> temp;
    list<char>::iterator it = grammar.grammarTable[i][j].begin();
    it++;
    for (it; it != grammar.grammarTable[i][j].end(); it++)
    {
        //如果没有出界，并且是非终结字符，并且FIRST集含有空字
        while (it != grammar.grammarTable[i][j].end() && isNonTerminal(*it) && hasEmpty(getNonTerminalIndex(*it)))
        {
            int index = getNonTerminalIndex(*it);
            set<char>::iterator itp = first.First[index].begin();
            for (itp; itp != first.First[index].end(); itp++)
            {
                //如果不是空字则添加temp集合
                if (!isEmpty(*itp))
                {
                    temp.insert(*itp);
                }
            }
            it++;
        }
        //没有出界
        if (it != grammar.grammarTable[i][j].end())
        {
            //如果是终结字符或空字，则把终结字符填到FIRST集
            if (isTerminal(*it) || isEmpty(*it))
            {
                temp.insert(*it);
                return temp;
            }
            //否则为非终结符
            else
            {
                int index = getNonTerminalIndex(*it);
                set<char>::iterator itpt = first.First[index].begin();
                for (itpt; itpt != first.First[index].end(); itpt++)
                {
                    temp.insert(*itpt);
                }
                return temp;
            }
        }
        //如果出界，则退出
        else
        {
            //说明都是非终结字符，且都含有空字
            temp.insert('@');
            return temp;
        }
    }
    return temp;
}
//将产生式字符转为字符串,i,j为相应产生式的索引
string charToString(int i, int j)
{
    char buf[100] = {0};
    int count = 0;
    list<char>::iterator it = grammar.grammarTable[i][j].begin();
    it++;
    for (it; it != grammar.grammarTable[i][j].end(); it++)
    {
        buf[count] = *it;
        count++;
    }
    buf[count] = '\0';
    string str(buf);
    return str;
}
//构建预测分析表
void bulidAnalyseTable()
{
    bool flag = false;
    //遍历每个非终结符
    for (int i = 0; i < grammar.count; i++)
    {
        //遍历每个非终结字符的产生式
        for (int j = 0; j < grammar.countEachRow[i]; j++)
        {
            flag = false;
            set<char> firstSet = buildFirstForOne(i, j);
            set<char>::iterator it = firstSet.begin();
            for (it; it != firstSet.end(); it++)
            {
                //如果FIRST集存在空字，记上标记
                if (isEmpty(*it))
                {
                    flag = true;
                }
                //否则将相应的产生式加入预测分析表
                else
                {
                    //将文法字符转为字符串
                    string str = charToString(i, j);
                    analyseTable[i][getTerminalIndex(*it)] = str;
                }
            }
            //产生式的FIRST集中含有空字
            if (flag)
            {
                //获取i为索引的非终结字符的FOLLOW集
                set<char>::iterator it = follow.Follow[i].begin();
                for (it; it != follow.Follow[i].end(); it++)
                {
                    if (isTerminal(*it))
                    {
                        analyseTable[i][getTerminalIndex(*it)] = (string) "@";
                    }
                }
            }
            //产生式的FIRST集中不含有空字
            else
            {
                //获取i为索引的非终结字符的FOLLOW集
                set<char>::iterator it = follow.Follow[i].begin();
                for (it; it != follow.Follow[i].end(); it++)
                {
                    analyseTable[i][getTerminalIndex(*it)] = (string) "match";
                }
            }
        }
    }
}
//打印预测分析表
void printAnalyseTable()
{
    cout << "预测分析表如下：" << endl;
    //占位符
    cout << setw(10) << " ";
    //循环输出每位终结符
    for (int i = 0; i < grammar.terNum; i++)
    {
        cout << setw(10) << grammar.terminalChar[i];
    }
    cout << endl;
    //输出每行
    for (int i = 0; i < grammar.count; i++)
    {
        //输出非终结字符
        cout << setw(10) << grammar.grammarTable[i][0].front();
        //输出相应的产生式
        for (int j = 0; j < grammar.terNum; j++)
        {
            cout << setw(10) << analyseTable[i][j];
        }
        cout << endl;
    }
    cout << endl;
}
//将vector中的字符转化为字符串
string veToString(vector<char> &vec)
{
    char buf[N] = {0};
    int index = 0;
    vector<char>::iterator it = vec.begin();
    for (it; it != vec.end(); it++)
    {
        buf[index] = *it;
        index++;
    }
    buf[index] = '\0';
    string str(buf);
    return str;
}
//将字符数组有选择的转化为字符串
string toString(char buf[], int start, int end)
{
    char temp[N];
    int index = 0;
    for (start; start <= end; start++)
    {
        temp[index] = buf[start];
        index++;
    }
    temp[index] = '\0';
    string str(temp);
    return str;
}
//核心函数，对语法进行分析
void Grammaranalyzer(string str)
{

    //将输入的字符串转化为字符数组
    char buf[N] = {0};
    strcpy(buf, str.c_str());
    //计算字符的数目
    int count = 0;
    for (int i = 0; buf[i] != 0; i++)
    {
        count++;
    }
    buf[count++] = '#';
    cout << setw(15) << "编号" << setw(15) << "符号栈" << setw(15) << "输入串" <<setw(15)<<""<< setw(15) << "所用产生式" << setw(15) << "动作"  << endl;
    //定义一个分析栈
    stack<char> analyseStack;
    //把'#'和文法开始符号入栈
    analyseStack.push('#');
    analyseStack.push(grammar.grammarTable[0][0].front());
    vector<char> vec;
    vec.push_back('#');
    vec.push_back(grammar.grammarTable[0][0].front());
    //把第一个字符读入a中
    char a = buf[0];
    //记录步骤
    int step = 0;
    cout << setw(15) << step << setw(15) << veToString(vec) << setw(15) << toString(buf, 0, count - 1) << setw(15) << " " << setw(15) << "初始化" << setw(15) << " " << endl;
    // buf[]的索引
    int index = 0;
    bool flag = true;
    while (flag)
    {
        char ch;
        if (!analyseStack.empty())
        {
            ch = analyseStack.top();
            analyseStack.pop();
            vec.pop_back();
        }
        if (isTerminal(ch) && ch != '#')
        {
            if (ch == a)
            {
                index++;
                a = buf[index];
                step++;
                cout << setw(15) << step << setw(15) << veToString(vec) << setw(15) << toString(buf, index, count - 1) << setw(15) << " " << setw(15) << (string) "GETNEXT(" + ch + (string) ")" << setw(15) << " " << endl;
            }
            else
            {
                //出错
                step++;
                cout << setw(15) << step << setw(15) << veToString(vec) << setw(15) << toString(buf, index, count - 1) << setw(15) << " " << setw(15) << (string) "pop" << setw(15) << "错误，栈顶终结符与输入符号不匹配 " << endl;
            }
        }
        else if (ch == '#')
        {
            if (ch == a)
            {
                flag = false;
                cout << "分析完成,输入串合法" << endl;
            }
            else
            {
                //出错
                cout << "出错";
                return;
            }
        }
        else if (isNonTerminal(ch))
        {
            string str = analyseTable[getNonTerminalIndex(ch)][getTerminalIndex(a)];
            //如果产生式不为空,且不为空字
            if (str != "@" && !str.empty() && str != "match")
            {

                int strSize = str.size();
                char temp[N];
                strcpy(temp, str.c_str());
                for (int i = strSize - 1; i >= 0; i--)
                {
                    analyseStack.push(temp[i]);
                    vec.push_back(temp[i]);
                }
                step++;
                cout << setw(15) << step << setw(15) << veToString(vec) << setw(15) << toString(buf, index, count - 1) << setw(15) << str << setw(15) << (string) "pop,push(" + str + (string) ")" << setw(15) << " " << endl;
            }
            //如果[M,a]为空,则跳过输入符号a
            else if (str.empty())
            {
                //出错
                index++;
                a = buf[index];
                step++;
                cout << setw(15) << step << setw(15) << veToString(vec) << setw(15) << toString(buf, index, count - 1) << setw(15) << " " << setw(15) << "错，跳过" << endl;
            }
            else if (str == "match")
            {
                //如果栈顶为文法开始符号,跳过输入符号
                if (ch == grammar.grammarTable[0][0].front())
                {
                    index++;
                    a = buf[index];
                    //文法开始符号入栈
                    analyseStack.push(ch);
                    vec.push_back(ch);
                    step++;
                    cout << setw(15) << step << setw(15) << veToString(vec) << setw(15) << toString(buf, index, count - 1) << setw(15) << " " << setw(15) << " " << setw(15) << "错，跳过" << endl;
                }
                else
                {
                    step++;
                    cout << setw(15) << step << setw(15) << veToString(vec) << setw(15) << toString(buf, index, count - 1) << setw(15) << " " << setw(15) << " " << setw(15) << (string) "错,M[" + ch + (string) "," + a + (string) "]=match" + "," + ch + (string) "已弹出栈" << endl;
                }
            }
            //若为空字，什么也不做
            else
            {
                step++;
                cout << setw(15) << step << setw(15) << veToString(vec) << setw(15) << toString(buf, index, count - 1) << setw(15) << ch + (string) "->" + (string) "@" << setw(15) << "空字匹配" << endl;
            }
        }
        else
        {
            //出错
            cout << "出错";
            return;
        }
    }
}